package com.wdc.sort;

public class BubbleSort {
    // 冒泡排序方法
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        
        // 外层循环控制所有的回合
        for (int i = 0; i < n - 1; i++) {
            swapped = false;

            // 内层循环进行相邻元素的比较和交换
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换元素
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            
            // 如果没有交换，数组已经有序，提前退出
        }
    }

    //优化版本的冒泡排序  用一个变量 x 来记录 交换的最后位置(右边界) 这样就可以减少冒泡轮数

    private static void optimizeBubble(int[] a) {
        int j = a.length - 1;
        int x = 0;
        while (true) {
            for (int i = 0; i < j; i++) {
                if (a[i] > a[i + 1]) {
                    int temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                }
                x = i;
            }
            j = x;
            if (j == 0) {
                break;
            }
        }
    }


    
    // 主方法，用于测试排序
    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};
        
        System.out.println("Original array:");
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();

        optimizeBubble(array);
        
        System.out.println("Sorted array:");
        for (int num : array) {
            System.out.print(num + " ");
        }



    }
}
